#include <vector>
#include <unordered_map>

using namespace std;

class Solution
{
public:
    vector<int> topKFrequent(vector<int> &nums, int k)
    {
        vector<int> res;                                          // 结果数组
        unordered_map<int, int> u_map;                            // 统计元素频率  <元素，频率>
        vector<vector<int>> Freq(nums.size() + 1, vector<int>()); // 元素出现次数对应的槽位
        // 1. 统计频率
        for (auto &num : nums)
        {
            ++u_map[num];
        }

        // 2. 把元素出现的次数，放到对应的槽位中: Freq[出现的次数] = {元素1， 元素2，...}
        for (auto &[num, count] : u_map)
        {
            Freq[count].push_back(num); // 例子：元素1 出现了，2次，那么就存储到下标为2的槽位
        }

        // 3. 从后往前遍历数组，就是k个高频元素
        for (int i = Freq.size() - 1; i >= 0; --i)
        {
            for (int j = 0; j < Freq[i].size(); ++j)
            {
                res.push_back(Freq[i][j]);
                if (res.size() == k)
                    return res;
            }
        }
        return res;
    }
};